package com.kingwood.algorithm.test200;

import java.util.Arrays;
import java.util.Scanner;


public class Wonderland {

    // 无论提交什么方法都带着这个数组      0  1  2 4
    public static int[] durations = { 1, 3, 7, 30 };

    /**
     * 获取最低花费 Wonderland
     * https://fcqian.blog.csdn.net/article/details/135328637
     * @param costs
     * @param days
     * @return
     */
    public static int getMinCosts(int[] costs, int[] days) {
        // 最大游玩日
        int maxDay = days[days.length - 1];
        int[] dp = new int[maxDay + 1];
        int index = 0;

        for (int i = 1; i <= maxDay; i++) {
            if (i == days[index]) {
                int buy1 = dp[i-1] + costs[0];
                int buy3 = (i >= 3 ? dp[i - 3] : 0) + costs[1];
                int buy7 = (i >= 7 ? dp[i - 7] : 0) + costs[2];
                int buy30 = (i >= 30 ? dp[i - 30] : 0) + costs[3];

                dp[i] = Math.min(buy1, Math.min(buy3, Math.min(buy7, buy30)));
                index++;
            } else {
                dp[i] = dp[i - 1];
            }
        }

        return dp[maxDay];
    }

    public static int getResult(int[] costs, int[] days) {
        return f(costs, days, 0);
    }

    public static int f(int[] costs, int[] days, int i) {
        if (i == days.length) {
            // 后续已经无旅行了
            return 0;
        }

        // i下标 : 第days[i]天，有一场旅行
        // i.... 最少花费是多少
        int ans = Integer.MAX_VALUE;
        for (int k=0, j=i; k<4; k++) {
            while (j < days.length && days[i] + durations[k] > days[j]) {
                // 因为方案2持续的天数最多，30天
                // 所以while循环最多执行30次
                // 枚举行为可以认为是O(1)
                j++;
            }

            ans = Math.min(ans, costs[k] + f(costs, days, j));
        }

        return ans;
    }

    public static int getResult2(int[] costs, int[] days) {
        int[] dp = new int[days.length];
        Arrays.fill(dp, Integer.MAX_VALUE);

        return f2(costs, days, 0, dp);
    }

    public static int f2(int[] costs, int[] days, int i, int[] dp) {
        if (i == days.length) {
            return 0;
        }

        if (dp[i] != Integer.MAX_VALUE) {
            return dp[i];
        }

        int ans = Integer.MAX_VALUE;
        for (int k = 0, j = i; k<4; k++) {
            while (j < days.length && days[i] + durations[k] > days[j]) {
                j++;
            }

            ans = Math.min(ans, costs[k] + f2(costs, days, j, dp));
        }

        dp[i] = ans;
        return ans;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int[] costs = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] days = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        System.out.println(getMinCosts(costs, days));
        System.out.println(getResult(costs, days));
        System.out.println(getResult2(costs, days));
    }
}
